package com.ztom.top100;

/**
 * 搜索二维矩阵 2
 * <p>
 * https://leetcode-cn.com/problems/search-a-2d-matrix-ii/
 *
 * @author ZhangTao
 */
public class Code70SearchMatrix {

    /**
     * 暴力
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix2(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        for (int[] nums : matrix) {
            for (int num : nums) {
                if (num == target) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 每行去二分查找
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix1(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        for (int[] nums : matrix) {
            if (search(nums, target) != -1) {
                return true;
            }
        }
        return false;
    }

    private int search(int[] nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        int mid = 0;
        while (l <= r) {
            mid = l + ((r - l) >> 1);
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }

    /**
     * Z 字形查找
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        // 左下角的数是所在行的最小值, 是所在列的最大值
        int r = m - 1;
        int c = 0;
        while (r >= 0 && c < n) {
            if (matrix[r][c] == target) {
                return true;
            } else if (matrix[r][c] > target) {
                r--;
            } else {
                c++;
            }
        }
        return false;
    }
}
